/**
 * 110. 平衡二叉树
 */
class Solution {
    public boolean isBalanced(TreeBinary.TreeNode root) {
        if(root == null){
            return true;
        }
        int left = maxDepth(root.left);//先求左树高度
        int right = maxDepth(root.right);//再求右树高度
        //最后求左右高度的绝对值小于2，同时满足左右的子树是平衡的
        return Math.abs(left - right) < 2 &&
               isBalanced(root.left)&&
               isBalanced(root.right);

    }
    public int maxDepth(TreeBinary.TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return left > right ? left+1 : right+1;
    }
}